package com.algo.tree;

import com.zhaofan.offer.No34;

import javax.swing.text.DefaultEditorKit;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树深度优先遍历
 */
public class IteraotrTree {
    TreeNode root;

    /**
     * 返回所有路径
     * @param root
     * @return
     */
    public List<List<TreeNode>> getAllPath(TreeNode root){
        return null;
    }



    public static void main(String[] args) {
        int a[]={1,3,2,6,7,4,5,8,9,11,12,23,33};
        IteraotrTree iteraotrTree = new IteraotrTree();
        iteraotrTree.insert(a);
        iteraotrTree.print(iteraotrTree.root);
    }


    public void print(TreeNode node){
        if(node==null){
            return;
        }
        System.out.print(node.val+",");
        print(node.left);


        print(node.right);
    }


    public void insert(int[] a){
        if(a.length==0 ) return;
        if(root==null){
            root=new TreeNode(a[0]);
        }

        LinkedList<TreeNode> list = new LinkedList<>();
        list.push(root);
        for (int i = 1; i < a.length; i++) {
            TreeNode node = list.peek();
            if(i%2==1){
                if(node.left!=null){
                    list.add(node.left);
                    i--;
                }else{
                    node.left = new TreeNode(a[i]);
                    list.add(node.left);
                }
            }else{
                if(node.right!=null){
                    list.add(node.right);
                    --i;
                }else{
                    node.right=new TreeNode(a[i]);
                    list.add(node.right);
                }
                list.poll();
            }
        }
    }


    public void each(TreeNode root){
        if(root==null){
            return ;
        }

        LinkedList<TreeNode> list = new LinkedList<>();

        while (!list.isEmpty()){
            TreeNode node = list.peek();
            if(node.left!=null){
                list.push(node.left);
            }else if(node.right!=null){
                list.push(node.right);
                list.poll();
            }else{
                list.poll();
            }
            System.out.println(node.val);
        }
    }



    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
